"""
难度：简单
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 递归方法
    # ·1 3 4 5 
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

    # 使用迭代方法
    def reverseList(self,head: ListNode) -> ListNode:
        pre ,cur = None,head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
        
